package com.sam.mooc;

import java.util.Arrays;

/**
 *
 *    1
 *   2 3
 *  4 5 6
 * 7 8 9 10
 *
 * 计算从顶点到边最大的和
 * Created by samwang on 2017/12/20.
 */
public class NumTriangleMaxSum {
    public static void main(String[] args) {
//        int[][] a = {{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}};
        int[][] a = {{1}};//, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}};
        int result = maxSum(a);
        System.out.println(result);
    }

    public static int maxSum(int[][] a) {
       for (int i = a.length - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                a[i][j] += Math.max(a[i + 1][j], a[i + 1][j + 1]);
            }
           System.out.println(Arrays.toString(a[i]));
       }

        return a[0][0];
    }

}
